//给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
//
// 叶子节点 是指没有子节点的节点。
//
//
//
// 示例 1：
//
//
//
//
//输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
//输出：[[5,4,11,2],[5,8,4,5]]
//
//
// 示例 2：
//
//
//
//
//输入：root = [1,2,3], targetSum = 5
//输出：[]
//
//
// 示例 3：
//
//
//输入：root = [1,2], targetSum = 0
//输出：[]
//
//
//
//
// 提示：
//
//
// 树中节点总数在范围 [0, 5000] 内
// -1000 <= Node.val <= 1000
// -1000 <= targetSum <= 1000
//
//
// 注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/
//
// Related Topics 树 深度优先搜索 回溯 二叉树 👍 428 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function pathSum(root: TreeNode | null, target: number): number[][] {

    function recur(node: TreeNode, sumGap: number, routeArr: number[]): void {
        //? 入结果的条件 必须是叶子节点且值相等
        if (
            node.left === null &&
            node.right === null &&
            sumGap === 0
        ) resArr.push([...routeArr]);
        //? 左不为空
        if (node.left !== null) {
            //? 差值再减
            sumGap -= node.left.val;
            routeArr.push(node.left.val);
            recur(node.left, sumGap, routeArr);
            //? 差值加回来 这就是回溯了
            sumGap += node.left.val;
            routeArr.pop();
        }
        //? 右不为空
        if (node.right !== null) {
            sumGap -= node.right.val;
            routeArr.push(node.right.val);
            recur(node.right, sumGap, routeArr);
            sumGap += node.right.val;
            routeArr.pop();
        }
    }
    const resArr: number[][] = [];
    if (root === null) return resArr;
    const routeArr: number[] = [];
    routeArr.push(root.val);
    //? 通过差值来判断
    recur(root, target - root.val, routeArr);
    return resArr;
};
//leetcode submit region end(Prohibit modification and deletion)
